﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

/* 思路：
1. key默认取left位置的值。
2. left指向区间最左边，right指向区间最后边，cur指向left+1位置。
3. cur遇到⽐key⼩的值后跟left位置交换，换到左边，left++，cur++。
4. cur遇到⽐key⼤的值后跟right位置交换，换到右边，right--。
5. cur遇到跟key相等的值后，cur++。
6. 直到cur>right结束
*/

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;

	int begin = left;
	int end = right;

	// 随机选基准值key
	int randi = left + (rand() % (right - left + 1));
	Swap(&arr[left], &arr[randi]);

	// 三路划分
	// left和right指向就是跟key相等的区间
	// [begin, left-1] [left, right] [right+1, end]
	int key = arr[left];
	int cur = left + 1;
	while (cur <= right)
	{
		// 1.cur遇到比key小，小的换到左边，同时把key换到中间位置
		// 2.cur遇到比key大，大的换到右边
		if (arr[cur] < key)
		{
			Swap(&arr[cur], &arr[left]);
			++left;
			++cur;
		}
		else if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right]);
			--right;
		}
		else
		{
			// cur位置的值与key相等，cur++，避免重复交换
			++cur;
		}
	}	

	// [begin, left-1] [left, right] [right+1, end]
	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, end);
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

int main()
{
	int a[] = { 6, 1, 7, 6, 6, 6, 4, 9 };
	int n = sizeof(a) / sizeof(a[0]);
	printf("排序前：\n");
	Print(a, n);
	QuickSort(a, 0, n - 1);
	printf("排序后：\n");
	Print(a, n);


	return 0;
}
